IGP (Interior Gateway Protocol) is known as a routing protocol of a network using an Internet protocol (which is referred to hereinafter as IP network). IGP is classified broadly into two types, which have different algorithms. One is called a distance vector type, and its typical protocol is RIP (Routing Information Protocol). In the distance vector algorithm, a route in which the number of router hops, i.e. the number of routers to pass through, between a transmission source and a destination is the smallest is selected. The other one is called a link-state type, and its exemplary protocol is OSPF (Open Shortest Path First routing). In the link-state protocol, topology information in a network system can be shared among all routers. The topology information is information about what routers exist in a system and by what links those routers are connected. Further, a router is called various names such as a relay device, a gateway device and a node.
In the link-state protocol, by using a directed graph which is generated from topology information, each router creates the shortest path tree from a path that achieves the minimum cost for each of the other routers, calculates the shortest path to a target destination, and determines the next transfer destination router with respect to each destination. Dijkstra algorithm is known as an algorithm for creating the shortest path tree. A series of shortest path selection and determination operations described above is called “route calculation” in the link-state protocol.